package com.leetcode.No0138;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * class Node {
 * int val;
 * Node next;
 * Node random;
 * <p>
 * public Node(int val) {
 * this.val = val;
 * this.next = null;
 * this.random = null;
 * }
 * }
 *
 * @program: leetcode
 * @description: 复制带随机指针的链表
 * @author: wangzhihua
 * @date: 2021-07-24
 */
public class Solution01 {

	@Test
	public void test01() {

	}

	public Node copyRandomList(Node head) {
		if (head == null) {
			return null;
		}

		ArrayList<Node> newNodeList = new ArrayList<Node>();
		HashMap<Node, Integer> oldNodeMap = new HashMap<Node, Integer>();

		Node tmpOldNode = head;
		while (tmpOldNode != null) {
			Node node = new Node(tmpOldNode.val);
			if (newNodeList.size() > 0) {
				newNodeList.get(newNodeList.size() - 1).next = node;
				newNodeList.add(node);
			} else {
				newNodeList.add(node);
			}
			oldNodeMap.put(tmpOldNode, newNodeList.size() - 1);
			tmpOldNode = tmpOldNode.next;
		}

		tmpOldNode = head;
		int index = 0;
		while (tmpOldNode != null) {
			newNodeList.get(index++).random = (tmpOldNode.random == null ? null : newNodeList.get(oldNodeMap.get(tmpOldNode.random)));
			tmpOldNode = tmpOldNode.next;
		}
		return newNodeList.get(0);
	}

	class Node {
		int val;
		Node next;
		Node random;

		public Node(int val) {
			this.val = val;
			this.next = null;
			this.random = null;
		}
	}
}
